package alo.p6.work4;

import org.junit.Test;
import alo.p3.ListNode;
import alo.p6.BinaryTreeNode;
import alo.p6.Ergodic;

/**
 * @ClassName SortedListToBST
 * @Description 有序单向链表转换为平衡二叉搜索树
 * @Author Fanxc
 * @DATE 2021/2/22 12:39
 * @Version 1.0
 */
public class SortedListToBST {
    ListNode listNode=null;//使用全局变量，用于链表后移
    BinaryTreeNode SortedListToBST(int start,int end) {
        if (start > end) {
            return null;
        }
        //两种mid的求法（用于数据为偶数个时）
//        int mid = (start+end+1) / 2;
        int mid = start+(end-start)/2;
        //中序遍历的顺序
        //左孩子
        BinaryTreeNode leftChild = SortedListToBST(start, mid - 1);
        //父节点
        BinaryTreeNode parent = new BinaryTreeNode();
        parent.setData(listNode.getData());
        parent.setLeft(leftChild);
        //右孩子
        listNode = listNode.getNext();
        parent.setRight(SortedListToBST(mid + 1, end));
        //向上返回结点，用于设置为其他结点的孩子
        return parent;
    }
    //方法，进行全局变量赋值，调用函数，返回平衡搜索树的根节点
    BinaryTreeNode SortedListToBST(ListNode head,int n){
        listNode=head;
        return SortedListToBST(0,n-1);
    }
    //测试
    @Test
    public void test() {
        ListNode head = new ListNode(0);
        ListNode node = head;
        for (int i = 1; i < 10; i++) {
            ListNode temp = new ListNode(i);
            node.setNext(temp);
            node=temp;
        }
        BinaryTreeNode root = SortedListToBST(head,10);
        new Ergodic().levelOrder(root);

    }
}
